LeetCode 67. Add Binary

67. Add Binary（二进制求和）

链接

https://leetcode-cn.com/problems/add-binary

题目

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “1”
输出: “100”
示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

思路

做起来比想象中麻烦不少，很多小细节需要注意。这里我直接用了一个StringBuilder来存储答案。
从后往前计算，num用于保存进位。若ab该位都存在，则二者加num为计算结果，num只有四种情况0123，01无进位，写入。23有进位，-2后写入，进位则置num为1否则为0，然后参与下一步运算。
如果ab都计算完了，num为1，则再产生进位，细节问题较多。

代码

  public static String addBinary(String a, String b) {
  StringBuilder ans = new StringBuilder();
  int len1 = a.length() - 1;
  int len2 = b.length() - 1;
  int num = 0;
  while (len1 >= 0 || len2 >= 0) {
    if (len1 >= 0) {
      num += a.charAt(len1) - '0';
      len1--;
    }
    if (len2 >= 0) {
      num += b.charAt(len2) - '0';
      len2--;
    }
    if (num < 2) {
      ans.insert(0, num);
      num = 0;
    } else {
      ans.insert(0, num - 2);
      num = 1;
    }
  }
  if (num == 1) {
    ans.insert(0, 1);
  }

  return ans.toString();
}